package daimasuixiangmu.btree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.Vector;

/**
 * TODO
 * 二叉树迭代便利
 * @author gaojiaxing
 * @version 1.0.0
 * @since 2021/05/27 22:06
 */
public class DieDaiBianLi {

  public static List<Integer> qianXuBiaLi(TreeNode root){
    List<Integer> rst = new ArrayList<>();
    Stack<TreeNode> vector = new Stack<>();

    if (root == null) {
      return rst;
    }
    rst.add(root.getVal());
    TreeNode left = root.getLeft();
    TreeNode right = root.getRight();
    while (left != null || right != null){
      if(right != null){
        vector.push(right);
      }
      if (left != null) {
        rst.add(left.getVal());
        right = left.getRight();
        left = left.getLeft();
      } else {
        left = null;
        right = null;
      }
    }
    System.out.println("---------- right --------- ");
    while (!vector.isEmpty()){
      root = vector.pop();
      rst.add(root.getVal());
      left = root.getLeft();
      right = root.getRight();
      while (left != null || right != null){
        if(right != null){
          vector.push(right);
        }
        if (left != null) {
          rst.add(left.getVal());
          right = left.getRight();
          left = left.getLeft();
        } else {
          left = null;
          right = null;
        }
      }
    }
    return rst;
  }

  public static List<Integer> qianXuBiaLi1(TreeNode root){
    List<Integer> rst = new ArrayList<>();
    Stack<TreeNode> vector = new Stack<>();
    if (root == null) {
      return rst;
    }
    vector.add(root);
    while (!vector.isEmpty()){
      TreeNode current = vector.pop();
      if (current != null) {
        rst.add(current.getVal());
        if (current.getRight() != null) {
          vector.add(current.getRight());
        }
        if (current.getLeft() != null) {
          vector.add(current.getLeft());
        }
      }
    }
    return rst;

  }

  public static List<Integer> zhongXuBiaLi(TreeNode root){
    List<Integer> rst = new ArrayList<>();
    Stack<TreeNode> vector = new Stack<>();
    if (root == null) {
      return rst;
    }
    vector.add(root);
    boolean preIsLeft = false;
    while (!vector.isEmpty()){
      TreeNode current = vector.pop();
      if (current != null) {
        if (preIsLeft) {
          if (current.getRight() != null) {
            preIsLeft = false;
          }
          rst.add(current.getVal());
          continue;
        }
        if (current.getRight() != null) {
          vector.add(current.getRight());
        }
        if (current.getLeft() != null) {
          vector.add(current);
          vector.add(current.getLeft());
        } else {
          if (current.getRight() == null) {
            preIsLeft = true;
          }
          rst.add(current.getVal());
        }
      }
    }

    return rst;
  }

  // xay --> yax --> xay
  // axy -->
  // xya

  public static void main(String[] args) {
    TreeNode root = new TreeNode(null,null,5);
    root.add(1);
    root.add(7);
    root.add(8);
    root.add(6);
    root.add(3);
    root.add(2);
    /**
     *         5
     *      /    \
     *     1     7
     *      \   / \
     *      3  6  8
     *     /
     *    2
     */
    List<Integer> rst = qianXuBiaLi1(root);
    // 5 1 3 2 7 6 8
    System.out.println(rst);

    rst = zhongXuBiaLi(root);
    // 1 2 3 5 6 7 8
    System.out.println(rst);

  }
}
